def heap_sort(arr: list):
  # 构建小顶堆（升序排序）
  for i in range(len(arr) // 2 - 1, -1, -1):
    adjust_heap(arr, len(arr), i)
  for i in range(len(arr) - 1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i]
    adjust_heap(arr, i, 0)
    print(arr)
  return arr


def adjust_heap(arr: list, heap_size: int, i: int):
  smallest = i
  l = 2 * i + 1
  r = 2 * i + 2
  if l < heap_size and arr[l] < arr[smallest]:
    smallest = l
  if r < heap_size and arr[r] < arr[smallest]:
    smallest = r
  if smallest != i:
    arr[i], arr[smallest] = arr[smallest], arr[i]
    adjust_heap(arr, heap_size, smallest)


if __name__ == "__main__":
  print(heap_sort([4, 5, 1, 6, 2, 7, 3, 8]))
